package q741_cherryPickup;

import java.util.Arrays;

public class Solution_1 {
    /*
    此题的难点在于当我们到达终点后还需要再走一次回到起点
    不妨将题目转换成有两个人同时从起点出发 最后走到终点最多能够摘取多少个樱桃
    问题在于如何将两个人的路线进行结合：
    首先两人的每人所走的总步数应为一致的 即 2 * n - 1 也就是从左上到右下的一条路的长度
    可以将两人设想为同时出发 构建dp数组为new int[n * 2 - 1][n][n];
    第一个维度代表一个人此时所走的总步数 第二第三个维度分别代表第一人和第二人此时向 右 所走的长度
    那么两个人向下所走的长度就可以通过 k - x1 和 k - x2 来判断
    因此可以构建两个人不同路线的动态规划
     */
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] f = new int[n * 2 - 1][n][n];
        for (int i = 0; i < n * 2 - 1; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(f[i][j], Integer.MIN_VALUE);
            }
        }
        f[0][0][0] = grid[0][0];
        for (int k = 1; k < n * 2 - 1; ++k) {
            for (int x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); ++x1) {
                int y1 = k - x1;
                if (grid[x1][y1] == -1) {
                    continue;
                }
                for (int x2 = x1; x2 <= Math.min(k, n - 1); ++x2) {
                    int y2 = k - x2;
                    if (grid[x2][y2] == -1) {
                        continue;
                    }
                    // 这里是寻找四种走法中的最大值 然后再进行dp转移

                    int res = f[k - 1][x1][x2]; // 都往右
                    if (x1 > 0) {
                        res = Math.max(res, f[k - 1][x1 - 1][x2]); // 往下，往右
                    }
                    if (x2 > 0) {
                        res = Math.max(res, f[k - 1][x1][x2 - 1]); // 往右，往下
                    }
                    if (x1 > 0 && x2 > 0) {
                        res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]); // 都往下
                    }

                    res += grid[x1][y1];
                    if (x2 != x1) { // 避免重复摘同一个樱桃
                        res += grid[x2][y2];
                    }
                    f[k][x1][x2] = res;
                }
            }
        }
        return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);
    }
}

